﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TSTreeSAX.fuctions
{
   public class LinList : ITraceable
    {
        protected int myCount = 0;    // Total number of elements
        protected SLink myFirst = null; // pointer to the First element
        protected SLink myLast = null; // pointer to the Last  element
        protected SLink myCurrent = null; // pointer to current (cached) element
        protected int myCurrent_index = -1;   // index (0..count-1) of current element
        //   -1 means undefined index
        protected Type myElementClass = null; // Class of the element
        /**
     * Default Constructor
     */
        public LinList()
        {
            try
            {
                this.myElementClass = Type.GetType("Object");
            }
            catch (TypeLoadException e)
            {
                Console.WriteLine(e);
            }
        }
        /**
         * Constructor
         */
        public LinList(Type elementClass) { this.myElementClass = elementClass; }
        //--------------------------------------------------------------------------
        /**
         * Print out the elements on stream
         */
        public void printOn()
        {
            Console.WriteLine(this.ToString() + ":");
            Console.WriteLine("  check         = " + (this.check() ? "OK" : "Fail"));
            Console.WriteLine("  count         = " + this.getNoOfElements());
            Console.Write("  enum get(i)   = [");
            for (int i = 0; i < this.getNoOfElements(); ++i)
                Console.Write(this.get(i) + " ");
            Console.WriteLine("]");
            Console.Write("  enum get_next = [");
            for (Object obj = this.getFirst(); obj != null; obj = this.getNext())
                Console.Write(obj + " ");
            Console.WriteLine("]");

            Console.Write("  enum get_prev = [");
            for (Object obj = this.getLast(); obj != null; obj = this.getPrev())
                Console.Write(obj + " ");
            Console.WriteLine("]");
            Console.WriteLine("  ToString()    = " + this.ToString());
            Console.WriteLine();
        }
        //--------------------------------------------------------------------------
        /**
         * Print out the elements on stream
         */
        public override String ToString()
        {
            String answer = this.ToString() + "(\n";
            for (Object obj = this.getFirst(); obj != null; obj = this.getNext())
                answer = answer + obj + "\n";
            answer = answer + ")";
            return answer;
        }
        //--------------------------------------------------------------------------
        /**
         * Return the total number of elements
         */
        public int getNoOfElements() { return this.myCount; }
        //--------------------------------------------------------------------------
        /**
         * Insert an object to beginning of list
         */
        public virtual void insert(Object obj)
        {
            //            *----*-next-> *-------*---------------
            //            | sd |        |myFirst|...............
            //null <-prev-*----* <-prev-*-------*---------------
            // allocate new Storage for object
            SLink sd = new SLink(obj);
            // Establish the links
            sd.next = this.myFirst;
            sd.prev = null;
            if (this.myFirst != null)
                this.myFirst.prev = sd;
            // adjust myFirst, myLast and myCount;
            ++this.myCount;
            this.myFirst = sd;
            if (this.myLast == null) //original list is empty
            {
                //for empty list, this.myFirst == this.myLast
                this.myLast = sd;
            }
            // reset current position and index
            this.myCurrent = null;
            this.myCurrent_index = -1;
            if (this.isTraceable())
            {
                Console.WriteLine("LinList.insert(" + obj + "): inserted to position first.");
                this.check();
            }
        }
        //--------------------------------------------------------------------------
        /**
         * Insert an object to end of list
         */
        public void append(Object obj)
        {
            //            *------*------*-next-> *----*-next-> null
            //            |......|myLast|        | sd |
            //null <-prev-*------*------* <-prev-*----*
            // allocate new Storage for object
            SLink sd = new SLink(obj);
            // Establish the links
            sd.next = null;
            sd.prev = this.myLast;
            if (this.myLast != null)
                this.myLast.next = sd;
            // adjust myFirst, myLast and myCount;
            ++this.myCount;
            this.myLast = sd;
            if (this.myFirst == null) //original list is empty
            {
                //for empty list, this.myFirst == this.myLast
                this.myFirst = sd;
            }
            // reset cuurent position and index
            this.myCurrent = null;
            this.myCurrent_index = -1;
            if (this.isTraceable())
            {
                Console.WriteLine("LinList.append(" + obj + "): inserted to position last.");
                this.check();
            }
        }
        /**
         * Erase an Object from the myCurrent position
         * Return:
         *   true  if successful
         *   false if no myCurrent object
         */
        public Boolean erase()
        {
            int original_index = this.myCurrent_index;
            SLink next_current = null;
            // Check for myCurrent element
            if (this.myCurrent != null)
            {
                if (this.myCurrent == this.myFirst)
                {
                    if (this.myFirst == this.myLast) //list has only one element
                    {
                        this.myFirst = this.myLast = null;
                        next_current = null;
                        this.myCurrent_index = -1;
                        if (this.isTraceable())
                        {
                            Console.WriteLine("LinList.erase(): the only element erased. List becomes empty.");
                        }
                    }
                    else //list has more than one element
                    {
                        // Remove myFirst element
                        this.myCurrent.next.prev = null;
                        this.myFirst = this.myCurrent.next;
                        next_current = this.myFirst;
                        this.myCurrent_index = 0;
                        if (this.isTraceable())
                        {
                            Console.WriteLine("LinList.erase(): first element erased.");
                        }
                    }
                }
                else
                {
                    if (this.myCurrent == this.myLast) // erase last element
                    {
                        this.myCurrent.prev.next = null;
                        this.myLast = this.myCurrent.prev;
                        next_current = null;
                        this.myCurrent_index = -1; //no element after original myLast
                        if (this.isTraceable())
                        {
                            Console.WriteLine("LinList.erase(): last element erased.");
                        }
                    }
                    else // erase current element
                    {
                        this.myCurrent.next.prev = this.myCurrent.prev;
                        this.myCurrent.prev.next = this.myCurrent.next;
                        next_current = this.myCurrent.next;
                        this.myCurrent_index++;
                        if (this.isTraceable())
                        {
                            Console.WriteLine("LinList.erase(): " + original_index + "-th element erased.");
                        }
                    }
                }
                //adjust myCurrent element
                this.myCurrent = next_current;
                // adjust the myCount
                --this.myCount;
                if (this.isTraceable())
                {
                    this.check();
                }

                return true;
            }
            if (this.isTraceable())
            {
                Console.WriteLine("LinList.erase(): current position not defined.");
                this.check();
            }
            return false;
        }
        //--------------------------------------------------------------------------
        /**
         * Retrieve an Object from the i-th element
         */
        public Object get(int i) //
        {
            Boolean ahead = true; // true if search forward
            // check the range of i
            if (i < 0 || i >= this.myCount)
                return null;
            // return the cached value
            if (i == this.myCurrent_index)
                return this.myCurrent.d;
            // if no cached value
            if (this.myCurrent_index == -1)
            {
                // determine whether desired element is near myFirst or myLast
                if (i < (this.myCount / 2))
                {
                    //Search forward from myFirst
                    this.myCurrent = this.myFirst;
                    this.myCurrent_index = 0;
                    ahead = true;
                }
                else
                {
                    //Search backward from myLast
                    this.myCurrent = this.myLast;
                    this.myCurrent_index = this.myCount - 1;
                    ahead = false;
                }
            }
            else
            {
                // die gewuenschte Position liegt vor der aktuellen
                if (i < this.myCurrent_index) // i.........myCurrent_index.......
                {
                    // liegt i naeher an myFirst, als an myCurrent_index?
                    if ((this.myCurrent_index - i) > i)
                    {
                        //i is far awary from myCurrent_index
                        //(myFirst)...(i)....|..........(myCurrent_index)
                        this.myCurrent = this.myFirst;
                        this.myCurrent_index = 0;
                        ahead = true;
                    }
                    else
                    {
                        //i is near myCurrent_index
                        //(myFirst)........|....(i).....(myCurrent_index)
                        ahead = false;
                    }
                }
                else // .........myCurrent_index.....i
                {
                    // liegt i naeher an myLast, als an myCurrent_index?
                    if ((i - this.myCurrent_index) > ((this.myCount - 1) - i))
                    {
                        //i is far awary from myCurrent_index
                        //(myCurrent_index).........|....(i)...(myLast)
                        this.myCurrent = this.myLast;
                        this.myCurrent_index = this.myCount - 1;
                        ahead = false;
                    }
                    else
                    {
                        //i is near myCurrent_index
                        //(myCurrent_index)....(i)....|........(myLast)
                        ahead = true;
                    }
                }
            }
            if (ahead) //search forward
            {
                for (int k = this.myCurrent_index; k < i; k++)
                {
                    if (this.myCurrent == null)
                    {
                        Console.WriteLine("LinList::get: List seems to be inconsistent");
                        Environment.Exit(1);
                    }
                    this.myCurrent = this.myCurrent.next;
                }
            }
            else  //search backward
            {
                for (int k = this.myCurrent_index; k > i; k--)
                {
                    if (this.myCurrent == null)
                    {
                        Console.WriteLine("LinList::get: List seems to be inconsistent");
                        Environment.Exit(1);
                    }
                    this.myCurrent = this.myCurrent.prev;
                }
            }
            this.myCurrent_index = i;
            return this.myCurrent.d;
        }
        //--------------------------------------------------------------------------
        /**
         * Retrieve the myFirst element w.r.t. myCurrent element
         * It also position the myCurrent pointer to myFirst element
         * Return an Object
         */
        public Object getFirst()
        {
            this.myCurrent = this.myFirst;
            if (this.myCurrent != null)
            {
                this.myCurrent_index = 0;
                return this.myCurrent.d;
            }
            else
                return null;
        }
        //--------------------------------------------------------------------------
        /**
         * Retrieve the myLast element w.r.t. myCurrent element
         * It also position the myCurrent pointer to myLast element
         * Return an Object
         */
        public Object getLast()
        {
            this.myCurrent = this.myLast;
            if (this.myCurrent != null)
            {
                this.myCurrent_index = this.myCount - 1;
                return this.myCurrent.d;
            }
            else
                return null;
        }
        //--------------------------------------------------------------------------
        /**
         * Retrieve the next element w.r.t. myCurrent element
         * It also position the myCurrent pointer to next element
         * Return an Object
         */
        public Object getNext()
        {
            this.myCurrent = this.myCurrent.next;
            if (this.myCurrent != null)
            {
                ++this.myCurrent_index;
                return this.myCurrent.d;
            }
            else
            {
                this.myCurrent_index = -1;
                return null;
            }
        }
        //--------------------------------------------------------------------------
        /**
         * Retrieve the previous element w.r.t. myCurrent element
         * It also position the myCurrent pointer to previous element
         * Return an Object
         */
        public Object getPrev()
        {
            this.myCurrent = this.myCurrent.prev;
            if (this.myCurrent != null)
            {
                --this.myCurrent_index;
                return this.myCurrent.d;
            }
            else
            {
                this.myCurrent_index = -1;
                return null;
            }
        }
        //--------------------------------------------------------------------------
        /**
         * Check integrity of list, true means list is valid
         */
        public virtual Boolean check()
        {
            SLink old_f = this.myFirst;
            // List must be completely empty
            if (old_f == null) //if pointer to myFirst element is null
            {
                if (this.myLast != null)//if pointer to myLast element is not null
                {
                    //inconsistent of myFirst and myLast
                    Console.WriteLine("LinList.check(): ERROR, myFirst == null but myLast != null.");
                    return false;
                }
                if (this.myCount != 0)
                {
                    //inconsistent of myFirst and myCount
                    Console.WriteLine("LinList.check(): ERROR, myFirst == null but myCount != 0.");
                    return false;
                }
                return true;
            }
            int i = 1;
            if (old_f.prev != null)
            {
                Console.WriteLine("LinList.check(): ERROR, myFirst.prev != null.");
                return false;
            }
            for (SLink f = old_f.next; f != null; f = f.next)
            {
                if (f.prev != old_f)
                {
                    Console.WriteLine("LinList.check(): ERROR, Incorrect backward link.");
                    return false;
                }
                if (old_f.next != f)
                {
                    Console.WriteLine("LinList.check(): ERROR, Incorrect forward link.");
                    return false;
                }
                old_f = f;
                i++;
                if (i > this.myCount)
                {
                    Console.WriteLine("LinList.check(): ERROR, Incorrect count,(myCount " + this.myCount + " < actual count " + i + ").");
                    return false;
                }
            }
            if (old_f.next != null)
            {
                Console.WriteLine("LinList.check(): ERROR, myLast.next != null.");
                return false;
            }
            if (this.myLast != old_f)
            {
                Console.WriteLine("LinList.check(): ERROR, myLast does not point to last element.");
                return false;
            }
            if (i != this.myCount)
            {
                Console.WriteLine("LinList.check(): ERROR, Incorrect count, (myCount " + this.myCount + " != actual count " + i + ").");
                return false;
            }
            return true;
        }
        //--------------------------------------------------------------------------
        /**
         * Implements the Traceable interface
         */
        private Boolean IamTraceable;
        public void setTraceable(Boolean enable) { this.IamTraceable = enable; }
        public Boolean isTraceable() { return this.IamTraceable; }
        //--------------------------------------------------------------------------
    }
}
